package org.example.myleet.p1269;

/**
 * 15 ms
 * 动态规划
 */
public class Solution {
    public int numWays(int steps, int arrLen) {
        int MOD7 = 1000000007;
        //注意maxColumn的作用，因为最远只能走step步，因此step步之外的数组长度是不用考虑的，此处选用较小的长度作为动态规划的边界
        int maxColumn = Math.min(steps, arrLen);
        //使用两个maxColumn + 2长度的数组，一个用来皴上一个步数的结果，另一个用来存当前步数的结果，+2的长度可以减少边界判断，即左边突出一个，右边突出一个
        long[][] dp = new long[2][maxColumn + 2];
        //初始化1
        dp[0][1] = 1;
        for (int i = 0; i < steps; ++i) {
            //记录当前可能方式数目的数组，偶数步使用1，奇数步使用0；上一步的数组就是另一个
            int thisI = (i & 1) == 0 ? 1 : 0;
            int lastI = thisI == 0 ? 1 : 0;
            for (int j = 0; j < maxColumn; ++j) {
                int thisJ = j + 1;
                //动态规划递推公式
                dp[thisI][thisJ] = dp[lastI][thisJ - 1] + dp[lastI][thisJ] + dp[lastI][thisJ + 1];
                if (dp[thisI][thisJ] > MOD7) {
                    //数值太大时进行取余
                    dp[thisI][thisJ] = dp[thisI][thisJ] % MOD7;
                }
            }
        }
        int thisI = ((steps - 1) & 1) == 0 ? 1 : 0;
        return (int) dp[thisI][1];
    }
}
